package LeetCode;

import java.util.List;

public class LC_139_WordBreak {
    public static void main(String[] args) {

    }

    public class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            int length = s.length();
            boolean[] words = new boolean[length];
            for (int i = 1; i <= length; i++) {
                int j;
                for (j = 0; j < i; j++) {
                    String substr = s.substring(j, i);
                    if (wordDict.contains(substr) && (j == 0 || words[j - 1])) {
                        words[i - 1] = true;
                        break;
                    }
                }
                if (j == i)
                    words[i - 1] = false;
            }
            return words[length - 1];
        }
    }

    public class Solution_2 {
        boolean wordBreak(String s, List<String> wordDict) {
            if (s.length() == 0)
                return false;
            if (wordDict.contains(s))
                return true;
            for (int i = 1; i <= s.length(); i++) {
                String substring = s.substring(0, i);
                if (wordDict.contains(substring) && wordBreak(s.substring(i), wordDict))
                    return true;
            }
            return false;
        }
    }
}
